This invention relates to scheduling of applications among processes in one or more associated computers; and, more particularly, to a scheduling system which implements a task schedule by setting operating system priorities for the processes working on queued activities to optimize usage of shared computer resources.
Scheduling of activities is needed when a computer is running multiple activities or applications. Assuming that each application or activity comprises more than one task, the tasks must be scheduled among available processes of the computer, often with the order of tasks being predetermined based upon the requirements of the application. For example, when doing a merge-sort operation, the tasks of sorting records into lists must be performed before the next task of merging the lists. The scheduling task becomes more challenging in a multi-processor parallel computing environment, where multiple tasks may be run simultaneously by associated processes. For optimal usage of the available resources, processes should have waiting tasks queued for commencement as soon as previous tasks have been completed, with xe2x80x9cwait statesxe2x80x9d being filled in with queued tasks.
In the past, load control has been used for multi-process scheduling. Under a load control scheduling scheme, only a subset of the total number of tasks are allowed to run at one time. If the processes for each of the subset of tasks all enter wait states (for example, pending the completion of a parallel-running task of the application by another process), the CPU will be unused throughout the duration of the wait states, even though there is more work queued. Scheduling of too few activities under the load control mechanism, therefore, frequently leads to under-utilization of the CPU. On the other hand, if too many activities are allowed to run at once under a load control scheme, which is done under the assumption that all activities will not enter wait states at the same time, the ability to schedule among all of the tasks which are running is lost.
Another scheduling method which has been used in the prior art is priority-based scheduling for management of computer resources. Under a priority-based scheduling scheme, an operating system scheduler prioritizes the workload and schedules one task to be active at any given time. For example, on the AIX* (* Trademark of International Business Machines Corporation) operating system, if applications A, B and C are to be scheduled in alphabetical order, and processes 1, 3 and 5 are working on A, 2 and 4 on B, and 6 on C, then processes 1, 3 and 5 have their operating system priorities set to 60, 2 and 4 to 61, and 6 to 62 (where lower process priority is more favorable). The prioritization scheme is effectively a resource utilization mechanism that does not perform scheduling of prioritized tasks among processes with the intent of running one or more applications as quickly and efficiently as possible.
When an activity to be scheduled does not parallelize into even amounts of work, neither load nor uniprocessor priority scheduling can maximize the application throughput. Database management systems, wherein the amount of work necessary for any task cannot be quantified in advance without detailed knowledge of the database and of the transactions to be performed thereon, defy scheduling by load or uniprocessor prioritization. Ideally, the scheduler must provide the ability to continue on to other activities related to the initial task when part of a parallel activity has been completed yet other related parts have not been completed.
What is desirable, therefore, is a dynamic priority scheduling mechanism for scheduling activities with multiple tasks among multiple processes, for minimizing unused CPU time.
It is therefore an objective of the present invention to implement scheduling at the task level.
It is additionally an objective of the present invention to provide multiple task scheduling which will minimize unused CPU time.
Still another objective of the invention is to provide coordination of activities among parallel computational resources to minimize unused CPU and optimize application run-time.
These and other objectives are realized by the present invention wherein a task schedule is enforced among multiple processes by setting process priorities based upon which tasks are running on which processes and based upon the task schedule. The task scheduling may be provided by a local or global scheduler which uses application information to prioritize tasks. The task schedule, or priority list, is provided at Local Activity Schedulers which schedule the activities for their local execution elements/nodes. Execution of activities locally are performed by any number of processes that reside in each execution element. These processes are assigned operating system priorities by the respective Local Activity Scheduler based on their assigned activities for execution and the task schedule.